Media storage services, such as a music or video “locker” service, can allow for storage of media in a network accessible storage service on behalf of a user. The media can be accessed via a computing device associated with an account of the user. For example, music can be streamed from a music locker service to a user's mobile device via a network. Accordingly, one way in which media can be established within a locker service in an account of the user involves the identification of media on a computing device of a user according to a fingerprint and signature. Once identified, the media can be associated with the user's account in the locker service without the need to actually upload or transmit copies of the media to the locker service from the user's computing device.